package 算法;

public class blockSearch {
    public static void main(String[] args) {
        /*
        分块查找
        核心思想：块内无序，块间有序。
        即为：分成的每一个小块内的元素顺序可以是乱的，但是块之间有序
        块之间的要求：每一个小块的最小值必须大于上一个小块的最大值（有序）
        实现步骤：1.创建数组blockArr存放每一块对象的信息
                2，先查找blockArr确定要查找的数据属于哪一块
                3.在单独的遍历这一块数据即可
                分块的思想：
                确保原数组的其他元素大于分块数组中的最大元素 a
         */
//        将数组分块  （分块的数目=数组长度开根号）
//        该数组有18个元素，开根号为4左右，即分成4个模块，每个模块大概有18/4个元素（可以进行具体的调整）
//          如下所示
        int[] arr={16,5,9,12,21,18,       //若按照常规方法，该行为21,18,32,23该行最大元素为32，下面几行的元素有比它小的，不符合规则，所以该行只有两个元素21,18.
                   32,23,37,26,45,34,  //所以此行元素一定包括26，但相较最大元素为37，下行有34，和上行相同，不符合规则
                   50,48,61,52,73,66};
//          若数据的分组元素差很多可以合并

        Block b1=new Block(21,0,5);//即调用下方class中的对象
        Block b2=new Block(37,6,11);
        Block b3=new Block(73,12,17);
//      定义数组用来管理三个块的对象
        Block[] blockArr={b1,b2,b3};
//        定义一个变量来记录查找的元素
            int number=73;
//            调用方法，索引传递表，数组，要查找的元素
        System.out.println(getIndex(blockArr,arr,number));
    }

    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        int indexBlock = findIndexBlock(blockArr, number);
        if (indexBlock==-1){
            System.out.println("查找的元素不在数组当中");
            return -1;
        }
//        indexBlock不为-1则说明数据在数组中
//        获得这一块数组的起始索引和结束索引进行遍历
        int startIndex=blockArr[indexBlock].getStartIndex();
        int endIndex=blockArr[indexBlock].getEndIndex();

//        遍历
        for (int i = startIndex; i <endIndex ; i++) {
            if (arr[i]==number){
                return i;
            }
        }
        return -1;
    }

//       确定number在索引的位置
private static int findIndexBlock(Block[] blockArr,  int number) {
    for (int i = 0; i < blockArr.length; i++) {
        if (number<=blockArr[i].getMax()){
            return i;
        }
    }
    return -1;
}
}
    class Block{
    private int max;
    private int startIndex;  //起始索引
    private int endIndex;   //结束索引

        public Block() {
        }

        public Block(int max, int startIndex, int endIndex) {
            this.max = max;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public int getMax() {
            return max;
        }

        public void setMax(int max) {
            this.max = max;
        }


        public int getStartIndex() {
            return startIndex;
        }


        public void setStartIndex(int startIndex) {
            this.startIndex = startIndex;
        }


        public int getEndIndex() {
            return endIndex;
        }


        public void setEndIndex(int endIndex) {
            this.endIndex = endIndex;
        }

        public String toString() {
            return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
        }
    }